package binarySearchTree

import (
	"math"
)

type node struct {
	value  int
	left   *node
	right  *node
	parent *node
}

type Tree struct {
	root   *node
	length int
}

func InsertNode(tree Tree, insertValue int) Tree {
	var currentNode *node
	var tmp *node
	if tree.length == 0 {
		currentNode = new(node)
		currentNode.value = insertValue
		tree.root = currentNode
		return tree
	} else {
		currentNode = tree.root
	}
	for {
		if currentNode.value < insertValue {
			//判断是否有右节点
			if currentNode.right == nil {
				tmp = new(node)
				tmp.value = insertValue
				currentNode.right = tmp
				tmp.parent = currentNode
				break
			} else {
				currentNode = currentNode.right
				continue
			}
		} else {
			if currentNode.left == nil {
				tmp = new(node)
				tmp.value = insertValue
				currentNode.left = tmp
				tmp.parent = currentNode
				break
			} else {
				currentNode = currentNode.left
				continue
			}
		}
	}
	return tree
}

//中序遍历
func LDR(tree Tree) []int {
	readList := make(map[int]int)
	i := 0
	var currentNode *node
	currentNode = tree.root
	data := make([]int, 0)
	for {
		if i == tree.length {
			break
		}
		if currentNode.left == nil {
			if readList[currentNode.value] == 1 {
				if readList[currentNode.right.value] == 1 {
					currentNode = currentNode.parent
					continue
				} else {
					currentNode = currentNode.right
					continue
				}
			} else {
				data = append(data, currentNode.value)
				readList[currentNode.value] = 1
				i++
				if currentNode.right == nil {
					currentNode = currentNode.parent
					continue
				} else {
					if readList[currentNode.right.value] == 1 {
						currentNode = currentNode.parent
						continue
					} else {
						currentNode = currentNode.right
						continue
					}
				}
			}
		} else {
			if readList[currentNode.left.value] == 1 {
				if readList[currentNode.value] == 1 {
					currentNode = currentNode.right
					continue
				} else {
					data = append(data, currentNode.value)
					readList[currentNode.value] = 1
					i++
					if currentNode.right == nil {
						currentNode = currentNode.parent
						continue
					} else {
						if readList[currentNode.right.value] == 1 {
							currentNode = currentNode.parent
							continue
						} else {
							currentNode = currentNode.right
							continue
						}

					}
				}
			} else {
				currentNode = currentNode.left
				continue
			}
		}
	}
	return data
}

func CreatTree(arrayList []int) Tree {
	myTree := Tree{}
	for i := 0; i < len(arrayList); i++ {
		myTree = InsertNode(myTree, arrayList[i])
		myTree.length++
	}
	return myTree
}
func TreeHeight(tree Tree) int {
	var hl = 1
	if tree.root.left != nil {
		hl = heightMax(tree.root.left, hl)
	}
	var hr = 1
	if tree.root.right != nil {
		hr = heightMax(tree.root.left, hr)
	}
	return int(math.Max(float64(hl), float64(hr)))
}

func heightMax(node *node, h int) int {
	var hL = h
	var hR = h
	if node.left == nil && node.right == nil {
		return h
	}
	if node.left != nil {
		h++
		hL = heightMax(node.left, h)
	}
	if node.right != nil {
		h++
		hR = heightMax(node.right, h)
	}
	return int(math.Max(float64(hL), float64(hR)))
}
